package cn.edu.jxau.test;

import java.util.Arrays;

/**
 * quick union实现
 * @author 付大石
 */
public class UnionFind {

    /**
     * 触点集
     */
    private int[] idArr;

    /**
     * 连通分量个数
     */
    private int count;

    public UnionFind(int count) {

        this.count = count;
        idArr = new int[count];
        for (int i = 0; i < idArr.length; i++) {
            idArr[i] = i;
        }
    }

    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    public int find(int p) {
        
        while(idArr[p] != p) {
            p = idArr[p];
        }
        return p;
    }

    public int count() {
        return count;
    }

    public void union(int p, int q) {
        
        int pRoot = find(p); //p连通分量
        int qRoot = find(q); //q连通分量
        if(pRoot == qRoot) {
            return ;
        }
        
        // 连接两个连通分量 //
        idArr[pRoot] = qRoot; //将p连通分量连到q连通分量上
        count--;
    }
    
    
    @Override
    public String toString() {
        
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("count:").append(count).append("\t");
        stringBuilder.append(Arrays.toString(idArr));
        return stringBuilder.toString();
    }
}
